#include <iostream>
#include <vector>
using namespace std;

int getMaxValue(int M, int N, vector<int>& weight, vector<int>& value) {
	// 创建二维数组dp，dp[i][j]表示前i种物品，背包容量为j时的最大总价值
	vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));
	
	// 动态规划求解
	for (int i = 1; i <= N; i++) { // 遍历物品
		for (int j = 1; j <= M; j++) { // 遍历背包容量
			if (j >= weight[i]) { // 当前物品能放入背包
				// 选择放入物品i或不放入物品i，取两者中的较大值
				dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
			} else { // 当前物品无法放入背包
				// 只能选择不放入物品i
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	
	return dp[N][M]; // 返回最大总价值
}

int main() {
	int M, N;
	cin >> M >> N;
	
	vector<int> weight(N + 1);
	vector<int> value(N + 1);
	
	for (int i = 1; i <= N; i++) {
		cin >> weight[i] >> value[i];
	}
	
	int result = getMaxValue(M, N, weight, value);
	cout <<"max=" <<result << endl;
	
	return 0;
}
